[Leetcode单排] 组合系列 (N39 N40 N77 N216)

字数统计: 1.5k阅读时长: 6 min

 2019/07/25  Share

39. Combination Sum

https://leetcode.com/problems/combination-sum/

给定一个目标值，以及一个数组，若从数组中取出若干个值能组成目标值的话即满足条件。这个题目有个重要的前提：数组中的值以及目标值都是正数。同时，题目还要求结果集要去重。如果只进行简单回溯，答案是会出现重复的，比如7的组成就有[2,2,3],[2,3,2],[3,2,2]，而答案只需其中之一。

大部分答案的做法是将数组排序后，定一个start值，后续递归只从下标为start的开始。但是实际上，不对数组进行排序答案依然是对的，原因在于，答案中避免重复真正要防止的是情况是：在某一轮递归中放入该值后，想隔一轮后递归轮次中又出现该值。比如这一轮递归中元素选择2，下一轮为3，再下一轮再继续选择2那就会出现重复。相同元素出现的递归轮次必须是靠在一起的。而只要做到这一点，你排序也好，不排也好，实际上对于获取正确答案都没有影响，只要满足数组中元素按一定顺序参与递归即可。

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    if (candidates == null || candidates.length == 0) {
        return null;
    }
    Arrays.sort(candidates); // 排序可有可无?
    List<List<Integer>> result = new ArrayList<>();
    handle(candidates, target, new ArrayList<>(), result, 0);
    return result;
}

private void handle(int[] candidates, int curValue, List<Integer> curList, List<List<Integer>> result, int start) {
    if (curValue == 0) {
        result.add(new ArrayList<>(curList));
        return;
    }
    if (curValue < 0) {
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        curList.add(candidates[i]);
        handle(candidates, curValue - candidates[i], curList, result, i);
        curList.remove(curList.size() - 1);
    }
}

那真的不用排序？当把不排序的代码丢进LeetCode判断时，答案虽是正确，但是时间排名较低。实际上，代码中一旦对数组进行排序，真正发挥排序作用是需要在for循环中加入这一段代码：if (candidates[i] > curValue) { return; }，一旦判断当前下标值比目标curValue大，直接结束此轮判断，即进行一次剪枝，这次数据量非常大的时候能起到作用。按这种做法，时间空间排名都是top。

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    if (candidates == null || candidates.length == 0) {
        return null;
    }
    Arrays.sort(candidates);
    List<List<Integer>> result = new ArrayList<>();
    handle(candidates, target, new ArrayList<>(), result, 0);
    return result;
}

private void handle(int[] candidates, int curValue, List<Integer> curList, List<List<Integer>> result, int start) {
    if (curValue == 0) {
        result.add(new ArrayList<>(curList));
        return;
    }
    // for 循环中既有判断，此处可省
    //if (curValue < 0) {
    //    return;
    // }
    for (int i = start; i < candidates.length; i++) {
        // 真正发挥排序作用的是这个判断
        if (candidates[i] > curValue) {
            return; // break 或 return
        }
        curList.add(candidates[i]);
        handle(candidates, curValue - candidates[i], curList, result, i);
        curList.remove(curList.size() - 1);
    }
}

40. Combination Sum II

https://leetcode.com/problems/combination-sum-ii/submissions/

与上题不同的是每个数字在每个组合中只能使用一次。整个流程大致上不变，只是有一些小变动，比如递归中每次下标为 i + 1，非 i。另外还有一个变动是剪枝去重的判断条件，即同一层中如果有相同元素则略过。

这个判断条件第一次写的时候，写成了 i > 0而非 i > s ，这样写会造成示例1的答案中少了[1,1,6]，这是因为 i = 1的时候，下标1和下标0的元素比较了。所以在每一次递归中，i 应该要比起始下标 s 大。

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    if (candidates == null || candidates.length == 0) {
        return null;
    }
    Arrays.sort(candidates);
    List<List<Integer>> result = new ArrayList<>();
    handle(candidates, target, 0, new ArrayList<>(), result);
    return result;
}

private void handle(int[] candidates, int target, int s, List<Integer> cur, List<List<Integer>> result) {
    if (target == 0) {
        result.add(new ArrayList<>(cur));
        return;
    }
    for (int i = s; i < candidates.length; i++) {
        if (candidates[i] > target) {
            return;
        }
        // 同一层中如果有相同元素则略过
        if (i > s && candidates[i] == candidates[i - 1]) {
            continue;
        }
        cur.add(candidates[i]);
        handle(candidates, target - candidates[i], i + 1, cur, result);
        cur.remove(cur.size() - 1);
    }
}

77. Combination

https://leetcode.com/problems/combinations/

标准组合，从 n 里面取 k 个元素。要注意数组里没有相同数值，且数组间要避免重复，比如[1,4]和[4,1]就是重复的。所以只需将当前加入到 cur 中的值加1放入到下一层递归即可。

public List<List<Integer>> combine(int n, int k) {
    if (n <= 0 || k <= 0) {
        return new ArrayList<>();
    }
    List<List<Integer>> result = new ArrayList<>();
    handle(n, k, 1, new ArrayList<>(), result);
    return result;
}

private void handle(int n, int k, int start, List<Integer> cur, List<List<Integer>> result) {
    if (cur.size() == k) {
        result.add(new ArrayList<>(cur));
        return;
    }
    for (int i = start; i <= n; i++) {
        cur.add(i);
        // 注意 i + 1 别写成 start + 1
        handle(n, k, i + 1, cur, result);
        cur.remove(cur.size() - 1);
    }
}

216. Combination Sum III

https://leetcode.com/problems/combination-sum-iii/submissions/

同样没什么可讲的了，只是要注意可以进行适当的优化，比如if (k == curList.size())。

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> result = new ArrayList<>();
    handle(k, n, 1, new ArrayList<>(), result);
    return result;
}

private void handle(int k, int curTotal, int start, List<Integer> curList, List<List<Integer>> result) {
    if (k == curList.size() && curTotal == 0) {
        result.add(new ArrayList<>(curList));
        return;
    }
    // optimize
    if (k == curList.size()) {
        return;
    }
    for (int i = start; i <= 9; i++) {
        if (curTotal < i) {
            return;
        }
        curList.add(i);
        handle(k,curTotal - i, i + 1, curList, result);
        curList.remove(curList.size() - 1);
    }
}

Next Post

[Leetcode单排] Letter Combinations of a Phone Number(N17)
Previous Post

[Leetcode单排] 排列系列（N46 N47 N784）

CATALOG

1. 39. Combination Sum
2. 40. Combination Sum II
1. 2.1. 77. Combination
2. 2.2. 216. Combination Sum III

